Computers in general use at present operate on the computational model developed by John von Neumann, in which a processor sequentially executes a list of instructions, one instruction at a time. Software in general use provides a means for a programmer to specify to the processor the instructions to be executed and their order of execution.
Unfortunately, there are physical constraints which limit the speed of a single von Neumann computing element. Predictions indicate that computer applications will require computational speeds greater than a single yon Neumann computing element can achieve.
In order to facilitate increased computational speed, parallel processing has been suggested. Networks of independent processors coupled by communication channels are commercially available. What is unavailable, however, is a suitable means for operating such networks to take advantage of the parallel processing which their structures permit. Conventional programming languages do not have the capability to control program execution on a plurality of processors, and there are limited methods for automatically converting existing programs written for conventional yon Neumann machines into a parallel-executable form.
Accordingly, languages or language extensions which contain the necessary control mechanisms might be developed to permit programs to be developed for parallel execution on multiprocessor systems. However, this solution has serious drawbacks. In particular, the programmer will be required to make assumptions as to the nature and number of computing elements in and topology of the network for which the programs are to be used. Such programs developed for one network would likely have to be substantially or entirely rewritten in order to run on other networks. Further, the speed increases obtained by such programs will be strongly determined by the skill of the programmer in selecting an algorithm and controlling the distribution of parallel components of the problem to be solved. While it may be possible for the programmer to adequately control the distribution and execution of a program for a network with a small number of processors, such control is likely to be intractable for large networks. Networks containing 1000 processors can be constructed from commercially available circuit boards, but it is unlikely that a programmer could adequately control execution of a program to take advantage of the processing capabilities of such a network. Finally, the speed of execution of the parallel components of programs will often be dependent on the data on which the programs operate. Since this cannot be determined in advance of execution of a program, in such circumstances it is impossible to optimize an algorithm for execution speed.
Programming languages have been developed which are largely machine-independent because they do not require control of the sequence of instruction execution. Such languages include logic programming languages, in which the problem is represented in the program as a set of logical facts and rules, in contrast with the lists of von Neumann procedures of conventional languages.
Others have proposed or developed logic program languages for use in multiprocessor networks. Commercially available parallel logic programs, however, have certain drawbacks. For instance, CS-Prolog requires the programmer to control the distribution of parallel portions of a program. Parsytec Prolog is similar in this respect, requiring the programmer to determine which portions of a program will be evaluated in parallel.
Another problem with the proposed and developed parallel processing methods is that they include compilation. Compiling has traditionally been used to maximize program execution speed, and accordingly the practice and suggestion of the prior art is to compile in the parallel processing context. Others have suggested parallel processing systems in which a logic program is extensively analyzed during compilation to determine all possible parallel execution paths. However, such an approach is based on the assumption that there will usually be more processors than parallel tasks, and therefore that the "overhead" execution time spent in identification of parallelism will be well spent. The assumption is believed by the inventor to be unwarranted, and that to the contrary, most problems will have sufficient parallelism to quickly saturate most networks. Accordingly, to optimize program execution speed, what is required is control of program execution to automatically operate the multiprocessor network at maximum efficiency for the particular program being executed and the particular network on which it is being executed.